package com.coder.algorithm.leetcode

import com.coder.algorithm.struct.ListNode

/**
 * [707. 设计链表](https://leetcode-cn.com/problems/design-linked-list/)
 *
 * @author yuhus
 * @date: 2022/3/30
 */
class l_0707 {
    /**
     * 哨兵头节点
     */
    private var head: ListNode = ListNode(0)

    fun get(index: Int): Int {
        var cur: ListNode? = head
        for (i in 0 .. index) {
            cur = cur?.next
        }
        return cur?.value ?: -1
    }

    fun addAtHead(`val`: Int) {
        val cur = ListNode(`val`)
        cur.next = head.next
        head.next = cur
    }

    fun addAtTail(`val`: Int) {
        var prev: ListNode? = head
        // prev.next == null break
        while (prev?.next != null) {
            prev = prev.next
        }
        prev?.next = ListNode(`val`)
    }

    fun addAtIndex(index: Int, `val`: Int) {
        var prev: ListNode? = head
        // cur 从0开始，prev 从1开始
        for (i in 1 .. index) {
            prev = prev?.next
        }
        val cur = ListNode(`val`)
        cur.next = prev?.next
        prev?.next = cur
    }

    fun deleteAtIndex(index: Int) {
        var prev: ListNode? = head
        // cur 从0开始，prev 从1开始
        for (i in 1 .. index) {
            prev = prev?.next
        }
        prev?.next = prev?.next?.next
    }

    fun toList(): List<Int> {
        val list = ArrayList<Int>()
        var cur: ListNode? = head.next
        while (cur != null) {
            list.add(cur.value)
            cur = cur.next
        }
        return list
    }
}